CF547C Mike and Foam

记 $c_i$ 为 $i$ 毫升泡沫的酒在架子上的瓶数，$A=\max_{i=1}^n a_i$。

为了方便将二元组视为有序，答案除以 $2$ 即可。

$\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]$

$\sum_{d=1}^A \mu(d) \sum_{i=1}^{A/d} \sum_{j=1}^{A/d} c_{id} c_{jd}$

$\sum_{d=1}^A \mu(d) ( \sum_{i=1}^{A/d}c_{id} )^2$

$\begin{cases} \Delta_+=\sum_{d|a_i} \mu(d) ((\sum_{i=1}^{A/d}c_{id}+1)^2-(\sum_{i=1}^{A/d}c_{id})^2) \\ \Delta_-=\sum_{d|a_i} \mu(d) ((\sum_{i=1}^{A/d}c_{id})^2-(\sum_{i=1}^{A/d}c_{id}-1)^2) \end{cases}$

$\begin{cases} \Delta_+=\sum_{d|a_i} \mu(d) (2\sum_{i=1}^{A/d}c_{id}+1) \\ \Delta_-=\sum_{d|a_i} \mu(d) (2\sum_{i=1}^{A/d}c_{id}-1) \end{cases}$

如果有多个 $1$ 上面的式子就 GG 了，不过这也很好处理，直接将答案减去/加上 $1$ 的个数即可。

时间复杂度 $\mathcal O(n+q\sqrt n)$

#include <cstdio>
#define LL long long

const int MAXN = 5e5;

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}

int n , q , a[ MAXN + 5 ] , c[ MAXN + 5 ];
LL Ans;
bool on[ MAXN + 5 ];

LL Calc[ MAXN + 5 ];
// int Calc( int d ) {
// 	int tmp = 0;
// 	for( int i = d ; i <= MAXN ; i += d ) tmp += c[ i ];
// 	return tmp;
// }
void Add( int x ) {
	for( int d = 1 ; d * d <= x ; d ++ )
		if( x % d == 0 ) {
			Ans += mu[ d ] * ( 2 * Calc[ d ] + 1 ) , Calc[ d ] ++;
			if( d * d != x ) Ans += mu[ x / d ] * ( 2 * Calc[ x / d ] + 1 ) , Calc[ x / d ] ++;
		}
	c[ x ] ++;
	if( x == 1 ) Ans --;
}
void Del( int x ) {
	for( int d = 1 ; d * d <= x ; d ++ )
		if( x % d == 0 ) {
			Ans -= mu[ d ] * ( 2 * Calc[ d ] - 1 ) , Calc[ d ] --;
			if( d * d != x ) Ans -= mu[ x / d ] * ( 2 * Calc[ x / d ] - 1 ) , Calc[ x / d ] --;
		}
	c[ x ] --;
	if( x == 1 ) Ans ++;
}

int main( ) {
	sieve();
	scanf("%d %d",&n,&q);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
	for( int i = 1 , pos ; i <= q ; i ++ ) {
		scanf("%d",&pos);
		on[ pos ] ? Del( a[ pos ] ) : Add( a[ pos ] );
		on[ pos ] ^= 1;
		printf("%lld\n", Ans / 2 );
	}
	return 0;
}